package com.zhugang.week11;


/**
 * @program algorithms
 * @description: lengthOfLIS
 * @author: chanzhugang
 * @create: 2022/09/05 18:50
 */
public class LengthOfLIS {

    /**
     * 300 最长递增子序列
     * 动态规划：其他问题模型
     *
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
        // 思路： 以nums[i]为结尾的序列的最大长度
        // 子序列是递增的
        // [10, 9, 2, 5, 3, 7, 101, 18]  [2, 3, 7, 101]  -> 长度为4

        /**
         * dp[i]记录以nums[i]为结尾的序列的最大长度
         * 那在这样一个递增子序列中(以nums[i]结尾)，上一个数字为nums[j] (0 <= j < i && nums[j-1] < nums[i]) 中的任意一个，
         * 所以: dp[i] = max(dp[j] + 1), 其中: 0 <= j < i && nums[j - 1] < nums[i]
         */

        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = 1;

        for (int i = 1; i < n; i++) {
            // 以第i个元素为结尾的最长递增子序列长度dp[i]
            dp[i] = 1;
            // 扫描i前面的
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        // 找最大值
        int result = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] > result) {
                result = dp[i];
            }
        }
        return result;
    }
}